Multi-threaded software provides multiple execution “threads” which act like independently executing programs. An advantage of such multi-threaded software is that each thread may be executed in parallel for improved speed of execution. For example, a computer server for the Internet may use a multi-threaded server program where each separate client transaction runs as a separate thread. A thread may include one set of operations and then the thread is terminated. Such a thread may process these operations using a single transaction and then terminate. However, most threads include a plurality of operations that are carried out using individual transactions.
Threads may need to modify common data shared among the threads. For example, in an implementation of a transaction based system (e.g., a hotel reservation system), multiple threads handling transactions for different entities may read and write common data. If the threads are not coordinated in their use of the common data, serious errors can occur. For example, a first thread may read a variable and then change that variable based on the needs of the thread's client. It is expected that the change to the variable will be visible to the other threads modifying common data of the transaction based system. However, if a second thread reads the same variable prior to the change by the first thread, the second thread may, based on that read, erroneously change that variable again, which results in inconsistent and erroneous common data of the transaction based system.
To avoid these problems, it is common to use synchronizing instructions to delineate portions of a thread (often called critical sections), where simultaneous execution by more than one thread might be a problem. A common set of synchronizing instructions implement a lock, using a lock variable having one value indicating that it is “held” by a thread and another value indicating that it is available. A thread or transaction of the thread must acquire the lock before executing the critical section and does so by reading the lock variable and if the lock variable is not held by another thread, writing a value to the lock variable indicating that it is held. When the critical section is complete, the thread writes to the lock variable a value indicating that the lock is available again or “free”.
Typically, the instructions used to acquire the lock are “atomic instructions”, that is, instructions that cannot be interrupted once begun by any other thread or quasi-atomic instructions that can be interrupted by another thread, but that make such interruption evident to the interrupted thread so that the instructions can be repeated.
While the mechanism of locking a critical section for use by a single thread, or a transaction of that thread, effectively solves conflict problems, that is, where two threads need to access a variable and at least one is writing, it can reduce the benefits of parallel execution of threads by forcibly serializing the threads as they wait for a lock. This serialization can be reduced by using a number of different locks associated, for example, with different small portions of shared memory. In this way, the chance of different threads waiting for a lock on a given portion of shared memory is reduced.
However, the use of multiple locks generally increases the complexity of the programming process and thus creates a tradeoff between program performance and program development time. Moreover, multiple locks or fine-grained locks may themselves cause performance problems, since managing the locks generally consumes a large amount of time.
Threads or transactions that attempt to acquire a variable, address, or memory location that is currently locked by another process are “blocked”. When a thread or transaction blocks, its processing is halted. Blocked threads or transactions are generally restarted or woken after a period of inactive time. For example, a thread management module may simply “wake” locked threads or transactions after a predetermined lapse of time. This allows the blocked thread or transaction to reattempt their processing requirements. If the variable, address, or memory location that is required by the woken thread or transaction is still locked, the thread or transaction blocks again and waits for an instruction to wake again.
A thread management module may wake the blocked threads or transactions using a round-robin process. A queue may be used for this purpose, where blocked threads or transactions are added to the queue and processed therefrom in turn. Blocked threads or transactions in the queue are selected from a head of the queue by the thread management module. The selected threads or transactions attempt to access relevant memory, and if successful, will commit. Those threads or transactions that encounter a lock are blocked again and placed back in the queue.
Another synchronization mechanism, which makes use of a “condition variable,” may be used for resolving data dependencies between threads, or thread transactions. The condition variable is a mechanism by which a thread blocks until an arbitrary condition has been satisfied. Another thread that makes the condition true is responsible for unblocking the waiting thread.
Functionally, the current management techniques for blocked threads achieve the necessary result of ensuring blocked threads or transactions are repeated until they are property processed and committed. However, significant processing may be wasted to achieve those results. In particular, the current management techniques often repeat blocked threads or transactions without ascertaining if there is a high likelihood that the repeated threads or transactions will process successfully. Furthermore, current management techniques generally require developers to establish explicit synchronization relationships for threads or transactions that have blocked. Establishing these explicit synchronization relationships is time consuming; moreover, intrinsic synchronization relationships cause application inefficiencies.
An additional problem with the current management techniques is that they generally require explicit programming in application program code. For example, in the case of locks, a developer must generally write instructions into the application program's code to acquire a lock before entering a specific critical section, and to release the lock when execution in the critical section is complete. This greatly complicates the programming task.